home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 028a / sq0928.zip / XSQ.C < prev    next >
C/C++ Source or Header  |  1990-09-13  |  27KB  |  1,032 lines
  1. /*% cc -M2 -compat -i -K -O % -o sq
  2.  *
  3.  *   xsq.c - CP/M compatible file squeezer utility
  4.  *
  5.  */
  6. static char *sccsid = "@(#)xsq.c         4.9 OMEN 09-12-90";
  7. /*
  8.  *            CHANGE HISTORY
  9.  *
  10.  * 4.9  Tweeks for compilation on VMS C
  11.  * 4.8  Preserves mod time of source file
  12.  * 4.7  Used stem() to shorten progress display
  13.  * 4.6    Eliminated "rescaling" message
  14.  * 4.5    Made likect static (bug fix)
  15.  * 4.4    Initialized keyptr for each file (bug fix).
  16.  * 4.3    Check for SQMAGIC in input file to detect already SQueezed file.
  17.  *    Added checks for write errors (disk full, etc.).
  18.  * 4.2    Q is appended to filenames with two letter extensions rather
  19.  *    than replacing second letter (file.11->file.11Q) to prevent some
  20.  *    filename collisions (file.11 .vs. file.12).
  21.  * 4.1    Microsoft doesn't know to right shift, so use a mask instead.
  22.  * 4.0  Added Cipher key feature. % compression now considers header.
  23.  * 2.1u Deleted Greenlaw's address per his request. Works with C86 2.00
  24.  *    but Lattice 2.0 results in bad files. Latest CC86 not tested.
  25.  * 2.0u Changes for VAX compatibility
  26.  * 2.0    Changes to allow operation with CC86 (CP/M-86) and
  27.  *    Lattice C (MS-DOS).
  28.  *    Lattice rewind() doesn't work
  29.  *    and a special hack is needed for binary files.
  30.  *    Added per cent compression display.
  31.  *    Fixed bug that caused short output files.
  32.  * 1.9    small changes for slightly faster squeezing. About
  33.  *    a third as fast as pack(1) (on the smae Unix machine).
  34.  * 1.7u machine independence was still lacking for 32-bit machines
  35.  *      like the VAX-11/780, so a typedef was added.  No action
  36.  *      need be taken if running on a 16-bit machine, but if
  37.  *      running on a VAX, define VAX either on the cc line or
  38.  *      in the program preamble.   Ben Goldfarb 12/13/82
  39.  * 1.6u machine independent output for file compatibility with
  40.  *    original CP/M version SQ, when running on machine with
  41.  *    IBM byte ordering such as Z8000 and 68000.
  42.  * 1.5u **nix version
  43.  *    Filename generation changed to suit **nix and stdio.
  44.  */
  45.  
  46. typedef short INT;
  47. typedef unsigned short UNSIGNED;
  48.  
  49. #ifdef vax11c   /*  we only want 16 bit integers  */
  50.  
  51. #include <types.h>
  52. #include <stat.h>
  53. #include <stdio.h>
  54. #include <signal.h>
  55.  
  56. #else
  57.  
  58. #include <stdio.h>
  59. #include <sys/types.h>
  60. #include <sys/stat.h>
  61. #include <signal.h>
  62.  
  63. #endif
  64.  
  65. #ifndef BREAD
  66. #define BREAD 0        /* Needed for some versions */
  67. #endif
  68.  
  69.  
  70. /*   ******  include file signal.h for non Unix(TM) systems
  71.  
  72.  #define SIG_IGN 1
  73.  #define SIG_DFL 0
  74.  #define signal(a,b) SIG_DFL
  75. ******************************************************   */
  76.  
  77. #define TRUE 1
  78. #define FALSE 0
  79. #define OK 0
  80. #define ERROR (-1)
  81. #define PATHLEN    312    /* Number of characters allowed in pathname */
  82. #define ALTNAME "sq.out"
  83.  
  84. /* Definitions and external declarations */
  85.  
  86. #define SQMAGIC  0xFF76        /* Magic word indicates a SQueezed file */
  87. #define KSQMAGIC 0xFF75        /* Cipher key magic word */
  88. #define KEYSIZE 4096        /* Max size of key file */
  89.  
  90. /* *** Stuff for first translation module *** */
  91.  
  92. #define DLE 0x90
  93.  
  94.  
  95. /* *** Stuff for second translation module *** */
  96.  
  97. #define SPEOF 256    /* special endfile token */
  98. #define NUMVALS 257    /* 256 data values plus SPEOF*/
  99.  
  100. /* Definitions and external declarations */
  101.  
  102. int Verbose;
  103. int Fullpathname;
  104. int Key;        /* flag for crypt key option */
  105.  
  106. unsigned char *Keyptr;
  107. unsigned char *Keyend;
  108. unsigned char Keybuf[KEYSIZE];
  109. char Keyname[PATHLEN];
  110.  
  111. UNSIGNED crc;    /* error check code */
  112. FILE *Inbuff, *Outbuff;    /* file buffers */
  113. long Inbytes, Outbytes;    /* counters for % compression calculation */
  114. INT Numnodes;        /* nbr of nodes in simplified tree */
  115.  
  116. /* *** Stuff for first translation module *** */
  117.  
  118. char state;         /* states */
  119. #define NOHIST    0     /* don't consider previous input*/
  120. #define SENTCHAR 1     /* lastchar set, no lookahead yet */
  121. #define SENDNEWC 2     /* newchar set, previous sequence done */
  122. #define SENDCNT 3     /* newchar set, DLE sent, send count next */
  123.  
  124. /* *** Stuff for second translation module *** */
  125.  
  126. #define NOCHILD -1    /* indicates end of path through tree */
  127. #define NUMNODES (NUMVALS + NUMVALS - 1)    /* nbr of nodes */
  128.  
  129. #define MAXCOUNT ((UNSIGNED ) ~0) /* biggest unsigned short integer */
  130.  
  131. /*
  132.  * The following array of structures are the nodes of the
  133.  * binary trees. The first NUMVALS nodes become the leaves of the
  134.  * final tree and represent the values of the data bytes being
  135.  * encoded and the special endfile, SPEOF.
  136.  * The remaining nodes become the internal nodes of the final tree.
  137.  */
  138.  
  139. struct    nd {
  140.     UNSIGNED weight;    /* number of appearances */
  141.     INT tdepth;        /* length on longest path in tre*/
  142.     INT lchild, rchild;    /* indices to next level */
  143. } node[NUMNODES];
  144.  
  145. INT dctreehd;    /* index to head node of final tree */
  146.  
  147. /*
  148.  * This is the encoding table:
  149.  * The bit strings have first bit in  low bit.
  150.  * Note that counts were scaled so code fits unsigned short integer
  151.  */
  152.  
  153. INT codelen[NUMVALS];            /* number of bits in code */
  154. UNSIGNED code[NUMVALS];        /* code itself, right adjusted */
  155. UNSIGNED tcode;            /* temporary code value */
  156.  
  157.  
  158. /* Variables used by encoding process */
  159.  
  160. INT curin;        /* Value currently being encoded */
  161. INT cbitsrem;        /* Number of code string bits remaining */
  162. UNSIGNED ccode;    /* Current code shifted so next code bit is at right */
  163.  
  164. /* This program compresses a file without losing information.
  165.  * The usq.com program is required to unsqueeze the file
  166.  * before it can be used.
  167.  *
  168.  * Typical compression rates are:
  169.  *    .EXE    12%
  170.  *    .C    33%
  171.  *    .DIC    46%    (uppercase and a few others)
  172.  *    .OUT    55%    (nroff output)
  173.  *    .PIC    80%    (files with long runs)
  174.  *
  175.  *  Calling the program without arguments gives usage info.
  176.  *
  177.  * The squeezed file name is formed by changing the second from last
  178.  * letter of the file type to Q. If there is no file type,
  179.  * the squeezed file type is Q. If the squeezed file name exists
  180.  * it is overwritten.
  181.  *
  182.  * The transformations compress strings of identical bytes and
  183.  * then encode each resulting byte value and EOF as bit strings
  184.  * having lengths in inverse proportion to their frequency of
  185.  * occurrence in the intermediate input stream. The latter uses
  186.  * the Huffman algorithm. Decoding information is included in
  187.  * the squeezed file, so squeezing small files or files with
  188.  * uniformly distributed byte values will actually increase size.
  189.  */
  190.  
  191.  
  192. /* special hack for Lattice C non-standard standard i/o */
  193. int _fmode = 0x8000;
  194.  
  195. int Inforeground = 1;
  196.  
  197. INT gethuff(), getc_crc(), portgetw();
  198. char *stem();
  199.  
  200. main(argc, argv)
  201. char *argv[];
  202. {
  203.     register i;
  204.     register char *cp;
  205.     register npats;
  206.     char **patts;
  207.     int n, errorstat;
  208.     FILE *kf;
  209.     if (signal(SIGINT, SIG_IGN)==SIG_IGN)
  210.         Inforeground = 0;
  211.     else
  212.         signal(SIGINT, SIG_DFL);
  213. #ifdef SIGHUP
  214.     signal(SIGHUP, SIG_IGN);
  215. #endif
  216.  
  217.     npats=0; errorstat=0;
  218.     if (argc<2)
  219.         goto usage;
  220.     while (--argc) {
  221.         cp = *++argv;
  222.         if (*cp == '-') {
  223.             while( *++cp) {
  224.                 switch(*cp) {
  225.                 case 'f':
  226.                     ++Fullpathname; break;
  227.                 case 'k':
  228.                     if (--argc < 1)
  229.                         goto usage;
  230.                     strcpy(Keyname, *++argv);
  231.                     if ( !(kf=fopen(Keyname, "r"))) {
  232.                         perror(Keyname);
  233.                         exit(0200);
  234.                     }
  235.                     i = fread(Keybuf, 1, KEYSIZE, kf);
  236.                     fclose(kf);
  237.                     if (i < 100) {
  238.                         fprintf(stderr, "sq: Key file read error");
  239.                         exit(0200);
  240.                     }
  241.                     fprintf(stderr, "sq: Keybuf %d bytes\n", i);
  242.                     Keyend = i + Keybuf;
  243.                     Key = TRUE;
  244.                     break;
  245.                 case 'v':
  246.                     Verbose=TRUE; break;
  247.                 default:
  248.                     goto usage;
  249.                 }
  250.             }
  251.         }
  252.         else if ( !npats && argc>0) {
  253.             if (argv[0][0]) {
  254.                 npats=argc;
  255.                 patts=argv;
  256.             }
  257.         }
  258.     }
  259.     if (npats < 1) {
  260. usage:
  261.         fprintf(stderr,"File squeezer %s\n\tAlogrithim by Richard Greenlaw\n", sccsid+4);
  262.         fprintf(stderr, "Usage: sq [-k Keyfile] [-f] pathname ...\n");
  263.         fprintf(stderr, "\t-k Encrypt output with Keyfile\n");
  264.         fprintf(stderr, "\t-f Fullpathname\n");
  265.         exit(1);
  266.     }
  267.     for (n=0; n<npats; ++n)
  268.         errorstat |= obey(patts[n]);
  269.     exit(errorstat != 0);
  270. }
  271.  
  272. obey(p)
  273. char *p;
  274. {
  275.     register char *q;
  276.     char outfile[PATHLEN+2];    /* output file spec. */
  277.  
  278.     Keyptr = Keybuf;
  279.     /* Build output file name */
  280.     strcpy(outfile, stem(p));
  281.     for (q = outfile; *q; ++q) {
  282.         if (*q == '.') {
  283.             if (*++q == '\0')
  284.                 *--q = '\0';    /* Kill trailing dot */
  285.             else {
  286.                 switch (*++q) {
  287.                 case '\0':
  288.                     *q = 'Q';
  289.                     *++q = '\0';
  290.                     goto qnamed;
  291.                 default:
  292.                     if (q[1] == '\0') {
  293.                         ++q; q[1] = '\0';
  294.                     }
  295.                     *q = 'Q';
  296.                     goto qnamed;
  297.                 }
  298.             }
  299.         }
  300.     }
  301.     /* No file type */
  302.     strcat(outfile, ".Q");
  303. qnamed:
  304.     if (strlen(outfile)>14)
  305.         return squeeze(p, ALTNAME);
  306.     else
  307.         return squeeze(p, outfile);
  308. }
  309.  
  310. squeeze(infile, outfile)
  311. char *infile, *outfile;
  312. {
  313.     register INT c;
  314.     struct stat st;
  315.     time_t SaveTimes[2];    /* save access & mod times here (sg) */
  316.  
  317.     if (Inforeground || Verbose)
  318.         fprintf(stderr, "%s -> %s: ", stem(infile), outfile);
  319.  
  320.     if (stat(infile, &st)) {
  321.         perror(infile); return ERROR;
  322.     }
  323.     if ((st.st_mode & S_IFMT) != S_IFREG) {
  324.         fprintf(stderr, "sq: %s is not a regular file\n", infile);
  325.         return ERROR;
  326.     }
  327.     if ((Inbuff=fopen(infile, "rb")) == NULL) {
  328.         perror(infile);
  329.         return ERROR;
  330.     }
  331.     switch (portgetw(Inbuff)) {        /* Check for header */
  332.     case KSQMAGIC:
  333.     case SQMAGIC:
  334.         if (Inforeground || Verbose)
  335.             fprintf(stderr, "already squeezed\n", infile);
  336.         else
  337.             fprintf(stderr,
  338.               "\r\nsq: %s is already squeezed\n", infile);
  339.         fclose(Inbuff);  return OK;
  340.     default:
  341.         fseek(Inbuff, 0L, 0);
  342.     }
  343.  
  344.     if ((Outbuff=fopen(outfile, "wb")) == NULL) {
  345.         perror(outfile);
  346.         fclose(Inbuff);  return ERROR;
  347.     }
  348.  
  349.     /* First pass - get properties of file */
  350.     crc = 0;    /* initialize checksum */
  351.     if (Inforeground || Verbose)
  352.         fprintf(stderr, "analyzing, ");
  353.     init_ncr();  init_huff();   
  354.  
  355.     /* Write output file header with decoding info */
  356.     Outbytes = wrt_head(Outbuff, infile);
  357.  
  358.     /* Second pass - encode the file */
  359.     clearerr(Inbuff); fseek(Inbuff, 0L, 0);  Inbytes=0;
  360.     if (Inforeground || Verbose)
  361.         fprintf(stderr, "squeezing, ");
  362.  
  363.     init_ncr();    /* For second pass */
  364.  
  365.     /* Translate the input file into the output file */
  366.     while((c = gethuff()) != EOF) {
  367.         ++Outbytes;
  368.         if (Key) {
  369.             c ^= *Keyptr;
  370.             if (++Keyptr >= Keyend)
  371.                 Keyptr = Keybuf;
  372.         }
  373. #ifdef DEBUG
  374.         printf("Transl: putc(%x)\n", c);
  375. #endif
  376.         if (putc(c, Outbuff) == ERROR && ferror(Outbuff)) {
  377.             fprintf(stderr, "sq: write error\n");
  378.             exit(0200);
  379.         }
  380.     }
  381.     if (ferror(Inbuff)) {
  382.         fprintf(stderr, "sq: read error\n");
  383.         exit(0200);
  384.     }
  385.     if (Inforeground || Verbose) {
  386. #ifdef DEBUG
  387.         fprintf(stderr, "%ld in %ld out ", Inbytes, Outbytes);
  388. #endif
  389.         if (Inbytes)
  390.             fprintf(stderr, "%ld%% compression, %d Nodes.\n",
  391.              ((Inbytes-Outbytes)*100L)/Inbytes, Numnodes);
  392.         else
  393.             fprintf(stderr, "Empty file.\n");
  394.     }
  395.     fclose(Inbuff);
  396.     fflush(Outbuff);
  397.     fclose(Outbuff);
  398. #ifndef vax11c
  399.     /*
  400.      * Under 4.2BSD (Sun) st_atime & st_mtime aren't contiguous, so the
  401.      * date gets screwed up, but this change should work anywhere.... (sg)
  402.      */
  403.     SaveTimes[0] = st.st_atime;       /* time of last access */
  404.     SaveTimes[1] = st.st_mtime;       /* time of last data modification */
  405.     utime(outfile, SaveTimes);
  406. #endif
  407.     return OK;
  408. }
  409.  
  410.  
  411. /* First translation - encoding of repeated characters
  412.  * The code is byte for byte pass through except that
  413.  * DLE is encoded as DLE, zero and repeated byte values
  414.  * are encoded as value, DLE, count for count >= 3.
  415.  */
  416.  
  417. init_ncr()    /* initialize getcnr() */
  418. {
  419.     state = NOHIST;
  420. }
  421.  
  422. INT
  423. getcnr()
  424. {
  425.     static INT likect;    /* count of consecutive identical chars */
  426.     static INT lastchar, newchar;
  427.  
  428.     switch(state) {
  429.     case NOHIST:
  430.         /* No relevant history */
  431.         state = SENTCHAR;
  432.         return (lastchar = getc_crc());
  433.     case SENTCHAR:
  434.         /* Lastchar is set, need lookahead */
  435.         switch(lastchar) {
  436.         case DLE:
  437.             state = NOHIST;
  438.             return 0;    /* indicates DLE was the data */
  439.         case EOF:
  440.             return EOF;
  441.         default:
  442.             for (likect=1; (newchar=getc_crc()) == lastchar && likect<255; ++likect)
  443.                 ;
  444.             switch(likect) {
  445.             case 1:
  446.                 return (lastchar = newchar);
  447.             case 2:
  448.                 /* just pass through */
  449.                 state = SENDNEWC;
  450.                 return lastchar;
  451.             default:
  452.                 state = SENDCNT;
  453.                 return DLE;
  454.             }
  455.         }
  456.     default:
  457.         fprintf(stderr,"sq: Internal Confusion - bad state\n");
  458.         exit(0200);
  459.     case SENDNEWC:
  460.         /* Previous sequence complete, newchar set */
  461.         state = SENTCHAR;
  462.         return (lastchar = newchar);
  463.     case SENDCNT:
  464.         /* Sent DLE for repeat sequence, send count */
  465.         state = SENDNEWC;
  466.         return likect;
  467.     }
  468. }
  469.  
  470.  
  471. /*
  472.  *    Second translation - bytes to variable length bit strings
  473.  *
  474.  * This translation uses the Huffman algorithm to develop a
  475.  * binary tree representing the decoding information for
  476.  * a variable length bit string code for each input value.
  477.  * Each string's length is in inverse proportion to its
  478.  * frequency of appearance in the incoming data stream.
  479.  * The encoding table is derived from the decoding table.
  480.  *
  481.  * The range of valid values into the Huffman algorithm are
  482.  * the values of a byte stored in an integer plus the special
  483.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  484.  *
  485.  * The "node" array of structures contains the nodes of the
  486.  * binary tree. The first NUMVALS nodes are the leaves of the
  487.  * tree and represent the values of the data bytes being
  488.  * encoded and the special endfile, SPEOF.
  489.  * The remaining nodes become the internal nodes of the tree.
  490.  *
  491.  * In the original design it was believed that
  492.  * a Huffman code would fit in the same number of
  493.  * bits that will hold the sum of all the counts.
  494.  * That was disproven by a user's file and was a rare but
  495.  * infamous bug. This version attempts to choose among equally
  496.  * weighted subtrees according to their maximum depths to avoid
  497.  * unnecessarily long codes. In case that is not sufficient
  498.  * to guarantee codes <= 16 bits long, we initially scale
  499.  * the counts so the total fits in an unsigned integer, but
  500.  * if codes longer than 16 bits are generated the counts are
  501.  * rescaled to a lower ceiling and code generation is retried.
  502.  */
  503.  
  504. /* Initialize the Huffman translation. This requires reading
  505.  * the input file through any preceding translation functions
  506.  * to get the frequency distribution of the various values.
  507.  */
  508.  
  509. init_huff()          
  510. {
  511.     register INT c;
  512.     register UNSIGNED *wp;        /* simplifies weight counting */
  513.     register UNSIGNED ceiling;    /* limit for scaling */
  514.     register INT i;
  515.     register INT listlen;            /* length of btlist */
  516.     static INT btlist[NUMVALS];    /* list of intermediate binary trees */
  517.  
  518.     /* Initialize tree nodes to no weight, no children */
  519.     init_tree();
  520.  
  521.     /* Build frequency info in tree */
  522.     while ((c = getcnr()) != EOF)
  523.         if (*(wp = &node[c].weight) !=  MAXCOUNT)
  524.             ++*wp;
  525.     ++node[SPEOF].weight;
  526.  
  527.     ceiling = MAXCOUNT;
  528.  
  529.     do {    /* Keep trying to scale and encode */
  530.         scale(ceiling);
  531.         ceiling /= 2;    /* in case we rescale */
  532.  
  533.         /* Build list of single node binary trees having
  534.          * leaves for the input values with non-zero counts
  535.          */
  536.         for (i = listlen = 0; i < NUMVALS; ++i)
  537.             if (node[i].weight) {
  538.                 node[i].tdepth = 0;
  539.                 btlist[listlen++] = i;
  540.             }
  541.  
  542.         /*
  543.          * Arrange list of trees into a heap with the entry
  544.          * indexing the node with the least weight at the top.
  545.          */
  546. #ifdef DEBUG
  547.         printf("calling heap: btlist= %d listlen= %d\n",
  548.         btlist, listlen);
  549. #endif
  550.         heap(btlist, listlen);
  551.  
  552.         /* Convert the list of trees to a single decoding tree */
  553.         bld_tree(btlist, listlen);
  554.  
  555.         /* Initialize the encoding table */
  556.         init_enc();
  557.  
  558.         /*
  559.          * Try to build encoding table.
  560.          * Fail if any code is > 16 bits long.
  561.          */
  562.     } 
  563.         while (buildenc(0, dctreehd));
  564.  
  565.     /* Initialize encoding variables */
  566.     cbitsrem = 0;    /* force initial read */
  567.     curin = 0;    /* anything but endfile*/
  568. }
  569.  
  570. /* The count of number of occurrances of each input value
  571.  * have already been prevented from exceeding MAXCOUNT.
  572.  * Now we must scale them so that their sum doesn't exceed
  573.  * ceiling and yet no non-zero count can become zero.
  574.  * This scaling prevents errors in the weights of the
  575.  * interior nodes of the Huffman tree and also ensures that
  576.  * the codes will fit in an unsigned integer. Rescaling is
  577.  * used if necessary to limit the code length.
  578.  */
  579.  
  580. scale(ceil)
  581. UNSIGNED ceil;    /* upper limit on total weight */
  582. {
  583.     register INT i;
  584.     register UNSIGNED w, sum;
  585.     register INT ovflw, divisor;
  586.     char increased;        /* flag */
  587.  
  588.     do {
  589.         for (i = sum = ovflw = 0; i < NUMVALS; ++i) {
  590.             if (node[i].weight > (ceil - sum))
  591.                 ++ovflw;
  592.             sum += node[i].weight;
  593.         }
  594.  
  595.         divisor = ovflw + 1;
  596.  
  597.         /* Ensure no non-zero values are lost */
  598.         increased = FALSE;
  599.         for (i = 0; i < NUMVALS; ++i) {
  600.             w = node[i].weight;
  601.             /* Don't fail to provide a code if it's used at all */
  602.             if (w < divisor && w != 0) {
  603.                 node[i].weight = divisor;
  604.                 increased = TRUE;
  605.             }
  606.         }
  607.     } 
  608.     while(increased);
  609.  
  610.     /* Scaling factor choosen, now scale */
  611.     if (divisor > 1)
  612.         for (i = 0; i < NUMVALS; ++i)
  613.             node[i].weight /= divisor;
  614. }
  615.  
  616. /* heap() and adjust() maintain a list of binary trees as a
  617.  * heap with the top indexing the binary tree on the list
  618.  * which has the least weight or, in case of equal weights,
  619.  * least depth in its longest path. The depth part is not
  620.  * strictly necessary, but tends to avoid long codes which
  621.  * might provoke rescaling.
  622.  */
  623.  
  624. heap(list, length)
  625. INT list[];
  626. INT length;
  627. {
  628.     register INT i;
  629.  
  630.     for (i = (length-2) / 2;   i >= 0;   --i)
  631.         adjust(list, i, length-1);
  632. }
  633.  
  634. /* Make a heap from a heap with a new top */
  635.  
  636. adjust(list, top, bottom)
  637. INT list[];
  638. register INT top, bottom;
  639. {
  640.     register INT k, temp;
  641.  
  642.     k = 2 * top + 1;    /* left child of top */
  643.     temp = list[top];    /* remember root node of top tree */
  644.     if ( k <= bottom) {
  645.         if ( k < bottom && cmptrees(list[k], list[k+1]))
  646.             ++k;
  647.  
  648.         /* k indexes "smaller" child (in heap of trees) of top */
  649.         /* now make top index "smaller" of old top and smallest child */
  650.         if (cmptrees(temp, list[k])) {
  651.             list[top] = list[k];
  652.             list[k] = temp;
  653.             /* Make the changed list a heap */
  654.             adjust(list, k, bottom); /* recursive*/
  655.         }
  656.     }
  657. }
  658.  
  659. /*
  660.  * Compare two trees, if a > b return true, else return false
  661.  * note comparison rules in previous comments.
  662.  */
  663.  
  664. cmptrees(a, b)
  665. register INT a, b;    /* root nodes of trees */
  666. {
  667.     if (node[a].weight > node[b].weight)
  668.         return TRUE;
  669.     if (node[a].weight == node[b].weight)
  670.         if (node[a].tdepth > node[b].tdepth)
  671.             return TRUE;
  672.     return FALSE;
  673. }
  674.  
  675. /* HUFFMAN ALGORITHM: develops the single element trees
  676.  * into a single binary tree by forming subtrees rooted in
  677.  * interior nodes having weights equal to the sum of weights of all
  678.  * their descendents and having depth counts indicating the
  679.  * depth of their longest paths.
  680.  *
  681.  * When all trees have been formed into a single tree satisfying
  682.  * the heap property (on weight, with depth as a tie breaker)
  683.  * then the binary code assigned to a leaf (value to be encoded)
  684.  * is then the series of left (0) and right (1)
  685.  * paths leading from the root to the leaf.
  686.  * Note that trees are removed from the heaped list by
  687.  * moving the last element over the top element and
  688.  * reheaping the smaller list.
  689.  */
  690.  
  691. bld_tree(list, len)
  692. INT list[];
  693. register INT len;
  694. {
  695.     register INT freenode;    /* next free node in tree */
  696.     register struct nd *frnp;    /* free node pointer */
  697.     register INT lch, rch;    /* temps for left, right children */
  698.  
  699.     /* Initialize index to next available (non-leaf) node.
  700.      * Lower numbered nodes correspond to leaves (data values).
  701.      */
  702.     freenode = NUMVALS;
  703.  
  704.     while(len > 1) {
  705.         /* Take from list two btrees with least weight
  706.          * and build an interior node pointing to them.
  707.          * This forms a new tree.
  708.          */
  709.         lch = list[0];    /* This one will be left child */
  710.  
  711.         /* delete top (least) tree from the list of trees */
  712.         list[0] = list[--len];
  713.         adjust(list, 0, len - 1);
  714.  
  715.         /* Take new top (least) tree. Reuse list slot later */
  716.         rch = list[0];    /* This one will be right child */
  717.  
  718.         /* Form new tree from the two least trees using
  719.          * a free node as root. Put the new tree in the list.
  720.          */
  721.         frnp = &node[freenode];    /* address of next free node */
  722.         list[0] = freenode++;    /* put at top for now */
  723.         frnp->lchild = lch;
  724.         frnp->rchild = rch;
  725.         frnp->weight = node[lch].weight + node[rch].weight;
  726.         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  727.         /* reheap list  to get least tree at top*/
  728.         adjust(list, 0, len - 1);
  729.     }
  730.     dctreehd = list[0];    /* head of final tree */
  731. }
  732.  
  733. /* ???????????? */
  734. maxchar(a, b)
  735. {
  736.     return ((a > b) ? a : b);
  737. }
  738. /* Initialize all nodes to single element binary trees
  739.  * with zero weight and depth.
  740.  */
  741.  
  742. init_tree()
  743. {
  744.     register INT i;
  745.  
  746.     for (i = 0; i < NUMNODES; ++i) {
  747.         node[i].weight = 0;
  748.         node[i].tdepth = 0;
  749.         node[i].lchild = NOCHILD;
  750.         node[i].rchild = NOCHILD;
  751.     }
  752. }
  753.  
  754. init_enc()
  755. {
  756.     register INT i;
  757.  
  758.     /* Initialize encoding table */
  759.     for (i = 0; i < NUMVALS; ++i) {
  760.         codelen[i] = 0;
  761.     }
  762. }
  763.  
  764. /* Recursive routine to walk the indicated subtree and level
  765.  * and maintain the current path code in bstree. When a leaf
  766.  * is found the entire code string and length are put into
  767.  * the encoding table entry for the leaf's data value.
  768.  *
  769.  * Returns TRUE if codes are too long.
  770.  */
  771.  
  772. unsigned mask[] = { 00,01,03,07,017,037,077,0177,0377,0777,01777,03777,07777,
  773.     017777,037777,077777,0177777,0177777,0177777,0177777,0177777,0177777,
  774.     0177777,0177777,0177777,0177777,0177777,0177777,0177777,
  775.     0177777,0177777,0177777,0177777,0177777,0177777,0177777,
  776.     0177777,0177777,0177777,0177777,0177777,0177777,0177777 };
  777.  
  778. buildenc(level, root)
  779. INT level;    /* level of tree being examined, from zero */
  780. INT root;     /* root of subtree is also data value if leaf */
  781. {
  782.     register INT l, r;
  783.  
  784.     l = node[root].lchild;
  785.     r = node[root].rchild;
  786.  
  787. #ifdef DEBUG
  788.     printf("buildenc: l= %d r= %d\n", l, r);
  789. #endif
  790.     if ( l == NOCHILD && r == NOCHILD) {
  791.         /*
  792.          * Leaf. Previous path determines bit string
  793.          * code of length level (bits 0 to level - 1).
  794.          * Ensures unused code bits are zero.
  795.          */
  796.         codelen[root] = level;
  797.         code[root] = tcode & mask[level];
  798. #ifdef DEBUG
  799.         printf("buildenc: code[root]= %x tcode= %x level= %d\n",
  800.         code[root],tcode,level);
  801. #endif
  802.         return (level > 16);
  803.     } 
  804.     else {
  805.         if ( l != NOCHILD) {
  806.             /* Clear path bit and continue deeper */
  807.             tcode &= ~(1 << level);
  808. #ifdef DEBUG
  809.             printf("tcode = %x ", tcode);
  810. #endif
  811.             /* NOTE RECURSION */
  812.             if (buildenc(level + 1, l))
  813.                 return TRUE;
  814.         }
  815.         if (r != NOCHILD) {
  816.             /* Set path bit and continue deeper */
  817.             tcode |= (1 << level);
  818.             /* NOTE RECURSION */
  819. #ifdef DEBUG
  820.             printf("tcode = %x ", tcode);
  821. #endif
  822.             if (buildenc(level + 1, r))
  823.                 return TRUE;
  824.         }
  825.     }
  826.     return FALSE;    /* if we got here we're ok so far */
  827. }
  828.  
  829. /* Write out the header of the compressed file */
  830.  
  831. wrt_head(ob, infile)
  832. FILE *ob;
  833. char *infile;    /* input file name (w/ or w/o drive) */
  834. {
  835.     register INT l,r;
  836.     register INT i, k;
  837.     char *p; int nob;
  838.  
  839.     putwe((Key?KSQMAGIC:SQMAGIC), ob);    /* identifies as compressed */
  840.     putwe(crc, ob);        /* unsigned sum of original data */
  841.     nob = 6;        /* include Numnodes */
  842.  
  843.     if (Key) {        /* Record key file name w/o drive */
  844.         p = stem(Keyname);
  845.         do {
  846.             putc(*p, ob); ++nob;
  847.         }
  848.             while (*p++);
  849.     }
  850.  
  851.     /* Record the original file name */
  852.     if (Fullpathname)
  853.         p = infile;
  854.     else
  855.         p = stem(infile);
  856.  
  857.     do {
  858.         putc(*p, ob); ++nob;
  859.     } 
  860.         while(*p++);
  861.  
  862.     /* Write out a simplified decoding tree. Only the interior
  863.      * nodes are written. When a child is a leaf index
  864.      * (representing a data value) it is recoded as
  865.      * -(index + 1) to distinguish it from interior indexes
  866.      * which are recoded as positive indexes in the new tree.
  867.      * Note that this tree will be empty for an empty file.
  868.      */
  869.  
  870.     Numnodes = (dctreehd < NUMVALS) ? 0 : dctreehd - (NUMVALS -1);
  871.     putwe(Numnodes, ob);
  872.  
  873.     for (k = 0, i = dctreehd; k < Numnodes; ++k, --i) {
  874.         l = node[i].lchild;
  875.         r = node[i].rchild;
  876.         l = (l < NUMVALS) ? -(l + 1) : dctreehd - l;
  877.         r = (r < NUMVALS) ? -(r + 1) : dctreehd - r;
  878.         putwe(l, ob);    /* left child */
  879.         putwe(r, ob);    /* right child */
  880.         nob += 4;
  881.     }
  882.     return nob;
  883. }
  884.  
  885. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  886.  *
  887.  * There are two unsynchronized bit-byte relationships here.
  888.  * The input stream bytes are converted to bit strings of
  889.  * various lengths via the static variables named c...
  890.  * These bit strings are concatenated without padding to
  891.  * become the stream of encoded result bytes, which this
  892.  * function returns one at a time. The EOF (end of file) is
  893.  * converted to SPEOF for convenience and encoded like any
  894.  * other input value. True EOF is returned after that.
  895.  */
  896.  
  897. INT        /*  Returns byte values except for EOF */
  898. gethuff()
  899. {
  900.     register rbyte;            /* Result byte value */
  901.     register need;            /* Numbers of bits */
  902.  
  903.     rbyte = 0;
  904.     need = 8;    /* build one byte per call */
  905.  
  906.     /*
  907.      * Loop to build a byte of encoded data
  908.      * Initialization forces read the first time
  909.      */
  910.  
  911. loop:
  912.     if (cbitsrem >= need) {
  913.         /* Current code fullfills our needs */
  914. #ifdef DEBUG
  915.         printf(" cbistrem=%d need=%d rbyte=%x\n",
  916.           cbitsrem, need, rbyte);
  917. #endif
  918.         if (need == 0)
  919.             return (rbyte&0377);
  920.         /* Take what we need */
  921.         rbyte |= (ccode << (8 - need));
  922.         /* And leave the rest */
  923.         ccode >>= need;
  924.         cbitsrem -= need;
  925. #ifdef DEBUG
  926.         printf(" returning need=%d rbyte=%x\n", need, rbyte);
  927. #endif
  928.         return (rbyte&0377);
  929.     }
  930.  
  931.     /* We need more than current code */
  932.     if (cbitsrem > 0) {
  933.         /* Take what there is */
  934.         rbyte |= (ccode << (8 - need));
  935.         need -= cbitsrem;
  936. #ifdef DEBUG
  937.         printf(" need more=%d rbyte=%x\n", need, rbyte);
  938. #endif
  939.     }
  940.     /* No more bits in current code string */
  941.     if (curin == SPEOF) {
  942.         /*
  943.          * The end of file token has been encoded. If
  944.          * result byte has data return it and do EOF next time
  945.          */
  946.         cbitsrem = 0;
  947.  
  948.         return (need == 8) ? EOF : (rbyte&0377);
  949.     }
  950.  
  951.     /* Get an input byte */
  952.     if ((curin = getcnr()) == EOF)
  953.         curin = SPEOF;    /* convenient for encoding */
  954.  
  955.     /* Get the new byte's code */
  956.     ccode = code[curin];
  957.     cbitsrem = codelen[curin];
  958. #ifdef DEBUG
  959.     printf("curin=%o ccode=%x cbitsrem=%d\n",
  960.     curin, ccode, cbitsrem);
  961. #endif
  962.  
  963.     goto loop;
  964. }
  965.  
  966.  
  967. /* Get next byte from file and update checksum */
  968.  
  969. INT
  970. getc_crc()
  971. {
  972.     register INT c;
  973.  
  974.     c = getc(Inbuff);
  975.     if (c != EOF) {
  976.         ++Inbytes;
  977.         crc += c;    /* checksum */
  978.     }
  979.     return c;
  980. }
  981.  
  982. /*
  983.  * Machine independent put-word that writes low order byte first
  984.  *  (compatible with CP/M original) regardless of host CPU type. 
  985.  */
  986. putwe(w, iob)
  987. register int w;
  988. register FILE *iob;
  989. {
  990.     Outbytes += 2;
  991.     putc(w, iob);
  992.     putc(w>>8, iob);
  993.     if (ferror(iob)) {
  994.         fprintf(stderr, "sq: write error\n");
  995.         exit(0200);
  996.     }
  997. }
  998.  
  999. /* Return pointer to file name part of pathname s */
  1000. char *
  1001. stem(s)
  1002. char *s;
  1003. {
  1004.     register char *p;
  1005.  
  1006.     for (p = s; *s; ) {
  1007.         switch (*s++) {
  1008.         case ':':
  1009.         case '/':
  1010.         case '\\':
  1011.             p = s;
  1012.         }
  1013.     }
  1014.     return p;
  1015. }
  1016.  
  1017. /*
  1018.  * Machine independent getw which always gets bytes in the same order
  1019.  *  as the CP/M version of SQ wrote them
  1020.  */
  1021. INT
  1022. portgetw(f)
  1023. register FILE *f;
  1024. {
  1025.     register short c;
  1026.  
  1027.     c = getc(f) & 0377;
  1028.     return (c | (getc(f) << 8));
  1029. }
  1030.  
  1031.  
  1032.